/*
Date:20210521 11:03AM
key:看不出来是最长公共子序列。
    注意初始化横纵列的方式，一直是0，碰1传递。
*/

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) 
    {
        int n=nums1.size();
        int m=nums2.size();
        int**A=new int*[n];
        for(int i=0;i<n;i++)
        {
            A[i]=new int[m];
        }
        for(int i=0;i<n;i++)
        {

           A[i][0]=1;
        }
        for(int i=0;i<n;i++)
        {
            if(nums1[i]!=nums2[0])
            {
                A[i][0]=0;
            }
            else{break;}
        }
        for(int i=0;i<m;i++)
        {
             A[0][i]=1;

        }
        for(int i=0;i<m;i++)
        {
            if(nums2[i]!=nums1[0])
            {
                A[0][i]=0;
            }
            else{break;}
        }
        //
        for(int i=1;i<n;i++)
        {
            for(int j=1;j<m;j++)
            {
                if(nums1[i]==nums2[j])
                {
                    A[i][j]=A[i-1][j-1]+1;
                }
                else
                {
                    A[i][j]=max(A[i][j-1],A[i-1][j]);
                }
            }
        }
        return A[n-1][m-1];
    }
};